home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / lisp / elk-2_0.lha / elk-2.0 / examples / scheme / Y < prev   
Encoding:
Text File  |  1989-02-17  |  5.8 KB  |  174 lines
  1. ; Date: 15 Nov 88 23:03:24 GMT
  2. ; From: uoregon!markv@beaver.cs.washington.edu  (Mark VandeWettering)
  3. ; Organization: University of Oregon, Computer Science, Eugene OR
  4. ; Subject: The Paradoxical Combinator -- Y (LONG)
  5. ; 
  6. ; Alternatively entitled:
  7. ;     "Y?  Why Not?" :-)
  8. ; 
  9. ; The discussion that has been going on in regards to the Y combinator as
  10. ; the basic operation in implementing recursive functions are interesting.
  11. ; The practical tests that people have made have shown that the Y
  12. ; combinator is orders of magnitude slower for implementing recursion than
  13. ; directly compiling it.
  14. ; 
  15. ; This is true for Scheme.  I hold that for an interesting set of
  16. ; languages, (lazy languages) that this result will not necessarily hold.
  17. ; 
  18. ; The problem with Y isn't its complexity, it is the fact that it is an
  19. ; inherently lazy operation.  Any implementation in Scheme is clouded by
  20. ; the fact that Scheme is an applicative order evaluator, while Y prefers
  21. ; to be evaluated in normal order.
  22. ; 
  23. ;     
  24.  (define Y
  25.    (lambda (g)    
  26.      ((lambda (h) (g (lambda (x) ((h h) x))))
  27.       (lambda (h) (g (lambda (x) ((h h) x)))))))
  28. ; 
  29.  (define fact
  30.    (lambda (f)
  31.      (lambda (n)
  32.        (if (= n 1)
  33.        1
  34.      (* n (f (- n 1)))))))
  35. ; 
  36. ; 
  37. ; Evaluating (Y fact) 2 results in the following operations in
  38. ; Scheme:
  39. ; 
  40. ; The argument is (trivially) evaluated, and returns two.
  41. ; (Y fact) must be evaluated.  What is it?  Y and fact each evaluate
  42. ; to closures.  When applied, Y binds g to fact, and executes the
  43. ; body.
  44. ; 
  45. ; The body is an application of a closure to another closure.  The
  46. ; operator binds h to the operand, and executes its body which....
  47. ; 
  48. ; Evaluates (g (lambda (x) ((h h) x))).  The operand is a closure,
  49. ; which gets built and then returns.  g evaluates to fact.  We
  50. ; substitute the closure (lambda (x) ((h h) x)) in for the function
  51. ; f in the definition of fact, giving...
  52. ; 
  53. ; (lambda (n)
  54. ;   (if (= n 1) 
  55. ;       1
  56. ;     (* n ((lambda (x) ((h h) x)) (- n 1)))))
  57. ; 
  58. ; Which we return as the value of (Y fact).  When we apply this to 2, we get
  59. ; 
  60. ; (* 2 ((lambda (x) ((h h) x)) 1))
  61. ; 
  62. ; We then have to evaluate
  63. ; ((lambda (x) ((h h) x)) 1)
  64. ; 
  65. ; or 
  66. ; ((h h) 1)
  67. ; 
  68. ; But remembering that h was (lambda (h) (g (lambda (x) ((h h) x)))), 
  69. ; we have 
  70. ; 
  71. ; (((lambda (h) (g (lambda (x) ((h h) x))))
  72. ;   (lambda (h) (g (lambda (x) ((h h) x)))))
  73. ;  1) ....
  74. ; 
  75. ; So, we rebind h to be the right stuff, and evaluate the body, which is
  76. ; 
  77. ; ((g (lambda (x) ((h h) x))) 1)
  78. ; 
  79. ; Which by the definition of g (still == fact) is just 1.
  80. ; 
  81. ; (* 2 1) = 2.
  82. ; 
  83. ; ########################################################################
  84. ; 
  85. ; Summary:  If you didn't follow this, performing this evaluation
  86. ; was cumbersome at best.  As far as compiler or interpreter is
  87. ; concerned, the high cost of evaluating this function is related
  88. ; to two different aspects:
  89. ; 
  90. ; It is necessary to create "suspended" values.  These suspended
  91. ; values are represented as closures, which are in general heap
  92. ; allocated and expensive.
  93. ; 
  94. ; For every level of recursion, new closures are created (h gets
  95. ; rebound above).  While this could probably be optimized out by a
  96. ; smart compiler, it does seem like the representation of suspended
  97. ; evaluation by lambdas is inefficient.
  98. ; 
  99. ;        
  100. ; ########################################################################
  101. ; 
  102. ; You can try to figure out how all this works.  It is complicated, I
  103. ; believe I understand it.  The point in the derivation above is that in
  104. ; Scheme, to understand how the implementation of Y works, you have to
  105. ; fall back on the evaluation mechanism of Scheme.  Suspended values must
  106. ; be represented as closures.  It is the creation of these closures that
  107. ; cause the Scheme implementation to be slow.
  108. ; 
  109. ; If one wishes to abandon Scheme (or at least applicative order
  110. ; evaluators of Scheme) one can typically do much better.  My thesis work
  111. ; is in graph reduction, and trying to understand better the issues having
  112. ; to do with implementation.
  113. ; 
  114. ; In graph reduction, all data items (evaluated and unevaluated) have the
  115. ; same representation: as graphs in the heap.  We choose to evaluate using
  116. ; an outermost, leftmost strategy.  This allows the natural definition of
  117. ; (Y h) = (h (Y h)) to be used.  An application node of the form:
  118. ; 
  119. ;                 @
  120. ;                / \
  121. ;               /   \
  122. ;              Y     h
  123. ; 
  124. ; can be constructed in the obvious way:
  125. ;                             @
  126. ;                / \
  127. ;               /   \
  128. ;              h     @
  129. ;                   /    \
  130. ;                  /   \
  131. ;                 Y     h
  132. ; 
  133. ; costing one heap allocation per level of recursion, which is
  134. ; certainly cheaper than the multiple allocations of scheme
  135. ; closures above.  More efficiently, we might choose to implement
  136. ; it using a "knot tying" version:
  137. ; 
  138. ; 
  139. ;                   /\
  140. ;                              /     \
  141. ;                 @     |
  142. ;                / \     /
  143. ;               /   \/
  144. ;              h
  145. ; 
  146. ; Which also works quite well.  Y has been eliminated, and will
  147. ; cause no more reductions.  
  148. ; 
  149. ; The basic idea is somehow that recursion in functional languages
  150. ; is analogous to cycles in the graph in a graph reduction engine.
  151. ; Therefore, the Y combinator is a specific "textual" indicator of
  152. ; the graph.
  153. ; 
  154. ; The G-machine (excellently described in Peyton Jones' book "The
  155. ; Implementation of Functional Programming Languages") also
  156. ; described the Y combinator as being efficient.  He chose letrecs
  157. ; as being a primitive in the extended lambda calculus.  His
  158. ; methodology behind compiling these recursive definitions was
  159. ; basically to compile fixed code which directly built these cyclic
  160. ; structures, rather than having them built at runtime.
  161. ; 
  162. ; I think (and my thesis work is evolving into this kind of
  163. ; argument) that Y is overlooked for trivial reasons.  Partial
  164. ; evaluation and smarter code generation could make an SK based
  165. ; compiler generate code which is equal in quality to that produced
  166. ; by supercombinator based compilation.
  167. ; 
  168. ; 
  169. ; This is too long already, ciao for now.
  170. ; 
  171. ; Mark VandeWettering
  172.  
  173. (print ((Y fact) 10))
  174.